package cgfsm;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import graphic.Graph;
import graphic.SubGraph;

/**
 * @author ZhangyiA
 * @describe:
 * @date 2021/07/21
 */

public class CGFSM {

    private Graph graph = null;
    private ArrayList<SubGraph> subGraphs;
    private Map<Integer , ArrayList<Integer>> freqSubGraph;
    private int tao ;

    public CGFSM(){
        this.freqSubGraph = new HashMap<>();
    }

    public CGFSM(Graph graph , int tao){
        this();
        this.graph = graph;
        this.tao = tao;
    }

    public void init(ArrayList<Integer> sizeOne){
        subGraphs = new ArrayList<>();
        for(int i = 0 ; i < sizeOne.size() ; i ++){
            SubGraph subGraph = new SubGraph(graph , i);
            subGraph.init(sizeOne.get(i));
            subGraphs.add(subGraph);
        }
        System.out.println("<1>. init finished !");
    }

    public void graphMining(){
        while(true){
            boolean flag = false;
            for(SubGraph subGraph : subGraphs){
                if(subGraph.extend()){ // 只要有一个子图扩展成功，仍需要进行下一次扩展
                    flag = true;
                }
            }
            subGraphPruning();
            if(subGraphs.size() != 0){
                for(SubGraph subGraph : subGraphs){
                    freqSubGraph.put(subGraph.getId() , new ArrayList<>(subGraph.vertex));
                }
            }
            if(!flag) break;
        }
    }

    public void subGraphPruning(){
        // 剪枝的同时向 freqSubGraph 添加频繁的图
        Map<String , ArrayList<SubGraph>> count = new HashMap<>();
        for(SubGraph subGraph : subGraphs){
            String nis = subGraph.getNIS();
            ArrayList<SubGraph> temp = count.containsKey(nis) ? count.get(nis) : new ArrayList<>();
            temp.add(subGraph);
            count.put(nis , temp);
        }
        Set<Integer> to_delete = new HashSet<>();
        for(Map.Entry<String , ArrayList<SubGraph>> entry : count.entrySet()){
            if(entry.getValue().size() < tao){
                for(SubGraph subGraph : entry.getValue()){
                    to_delete.add(subGraph.getId());
                }
                continue;
            }
            for(int i = 0 ; i < entry.getValue().size(); i ++){
                int cnt = 1;
                SubGraph s1 = entry.getValue().get(i);
                if(to_delete.contains(s1.getId())) continue;
                for(int j = 0 ; j < entry.getValue().size() ; j ++){
                    if (j == i) continue;
                    SubGraph s2 = entry.getValue().get(j);
                    if(to_delete.contains(s2.getId())) continue;
                    if(s1.getDegree() == s2.getDegree() && equalsEdgeLabel(s1 , s2) && equalsVertexLabel(s1 , s2)){
                        cnt ++ ;
                        if(haveIncludeSameVertex(s1 , s2)){
                           if(!to_delete.contains(s1.getId()) && !to_delete.contains(s2.getId())){
                               to_delete.add(s2.getId());
                           }
                        }
                    }
                }
                if(cnt < tao) to_delete.add(s1.getId());
            }
        }
        for(int i = 0 ; i < subGraphs.size() ; i ++){
            if(to_delete.contains(subGraphs.get(i).getId())){
                subGraphs.remove(i);
                i --;
            }
        }
    }

    public boolean equalsEdgeLabel(SubGraph sg1 , SubGraph sg2){
        if(sg1.edgeLabelCount.size() != sg2.edgeLabelCount.size()) return false;
        for(Map.Entry<Integer , Integer> entry : sg2.edgeLabelCount.entrySet()){
            // 先看 sg1 是否包含该标签 , 包含了再看改标签出现的次数是否相等
            if(!sg1.edgeLabelCount.containsKey(entry.getKey()) || !(sg1.edgeLabelCount.get(entry.getKey()).equals(entry.getValue())) )
                return false;
        }
        return true;
    }

    public boolean equalsVertexLabel(SubGraph sg1 , SubGraph sg2){
        if(sg1.vertexLabelCount.size() != sg2.vertexLabelCount.size()) return false;
        for(Map.Entry<Integer , Integer> entry : sg2.vertexLabelCount.entrySet()){
            // 先看 sg1 是否包含该标签 , 包含了再看改标签出现的次数是否相等
            if(!sg1.vertexLabelCount.containsKey(entry.getKey()) || !(sg1.vertexLabelCount.get(entry.getKey()).equals(entry.getValue())) )
                return false;
        }
        return true;
    }

    public boolean haveIncludeSameVertex(SubGraph sg1 , SubGraph sg2){
        for(int v1 : sg1.vertex){
            for(int v2 : sg2.vertex){
                if(v1 == v2) return true;
            }
        }
        return false;
    }

    public void printFreSubGraph(){
        System.out.println("final: all frequent subgraph ");
        for(Map.Entry<Integer , ArrayList<Integer>> entry : freqSubGraph.entrySet()){
            System.out.print(entry.getKey() + "  " + entry.getValue() + "  [ ");
            for(int num : entry.getValue()){
                System.out.print(graph.vertices[num].getLabel() + " ");
            }
            System.out.print("]\n");
        }
    }

}
